package com.lfg.leetcode.leetcode300;


public class No327countRangeSum {
    public static void main(String[] args) {
        int[] nums = {-2, 5, -1};
        System.out.println(countRangeSum3(nums, -2, 2));
        System.out.println(countRangeSum5(nums, -2, 2));
        System.out.println(countRangeSum3(new int[]{-2147483647, 0, -2147483647, 2147483647}, -564, 3864));
        System.out.println(countRangeSum5(new int[]{-2147483647, 0, -2147483647, 2147483647}, -564, 3864));
    }


    private static int sort(long[] sums, int from, int to, int lower, int upper) {
        if (from > to) return 0;
        if (from == to) return (lower <= sums[from] && sums[from] <= upper) ? 1 : 0;
        int count = 0;
        int m = (from + to) / 2;
        count = sort(sums, from, m, lower, upper) + sort(sums, m + 1, to, lower, upper);
        for (int i = from, j = m + 1, k = m + 1; i <= m; i++) {

            while (j <= to && sums[j] - sums[i] < lower) j++;
            while (k <= to && sums[k] - sums[i] <= upper) k++;
            count += k - j;
        }
        long[] merged = new long[to - from + 1];
        int l = from, r = m + 1;
        for (int i = 0, j = from, k = m + 1; i < merged.length; i++) {
            if (j > m) merged[i] = sums[k++];
            else if (k > to) merged[i] = sums[j++];
            else if (sums[j] <= sums[k]) merged[i] = sums[j++];
            else merged[i] = sums[k++];
        }
        System.arraycopy(merged, 0, sums, from, merged.length);
        return count;
    }

    public static int countRangeSum5(int[] nums, int lower, int upper) {
        if (nums == null || nums.length == 0) return 0;
        long[] sums = new long[nums.length];
        sums[0] = nums[0];
        for (int i = 1; i < nums.length; i++) sums[i] = sums[i - 1] + nums[i];
        return sort(sums, 0, sums.length - 1, lower, upper);
    }


    public static int countRangeSum3(int[] nums, int lower, int upper) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            long cnt = 0;
            for (int j = i; j < nums.length; j++) {
                cnt += nums[j];
                if (cnt <= upper && cnt >= lower) {
                    count++;
                }
            }
        }
        return count;
    }


    public static int countRangeSum(int[] nums, int lower, int upper) {
        int count = 0;
        if (nums.length == 0) {
            return count;
        }
        if (upper < lower) {
            return 0;
        }
        long[] sum = new long[nums.length];
        sum[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            sum[i] = nums[i] + sum[i - 1];
        }
        Node root = null;
        for (int i = 0; i < sum.length; i++) {
            if (lower <= sum[i] && sum[i] <= upper) {
                count++;
            }
            if (root == null) {
                root = new Node(sum[i]);
            } else {
                long start = sum[i] - upper;
                long end = sum[i] - lower;
                count += root.count(root, start, end);
                root.insert(root, sum[i]);
            }
        }
        return count;
    }


    static class Node {
        long val;
        int count = 1;
        Node left;
        Node right;

        Node(long val) {
            this.val = val;
        }

        public int count(Node root, long lower, long upper) {
            int count = 0;
            if (root == null) {
                return count;
            } else if (root.val < lower) {
                count += count(root.right, lower, upper);
            } else if (root.val > upper) {
                count += count(root.left, lower, upper);
            } else {
                count += count(root.left, lower, root.val - 1) + count(root.right, root.val + 1, upper) + root.count;
            }
            return count;
        }

        public void insert(Node root, long val) {
            if (root == null) {
                return;
            }
            if (root.val == val) {
                root.count++;
            } else if (root.val < val) {
                if (root.right == null) {
                    root.right = new Node(val);
                    return;
                }
                insert(root.right, val);
            } else {
                if (root.left == null) {
                    root.left = new Node(val);
                    return;
                }
                insert(root.left, val);
            }
        }

    }


}



